import org.junit.Test;

public class day01 {
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //官方解法1：递归
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
        /*//我的迭代
        if(list1 == null | list2 == null) return list1 == null ? list2:list1;
        ListNode merge = new ListNode(-1);
        ListNode pre = merge;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                pre.next = list1;
                list1 = list1.next;
            }else{
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2:list1;
        return merge;*/
        /*//官方解法：迭代
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = list1 == null ? list2 : list1;

        return prehead.next;

         */
    }
    @Test
    public void test1(){
        ListNode list1 = new ListNode(1,
                            new ListNode(2,
                                new ListNode(4)));
        ListNode list2 = new ListNode(1,
                            new ListNode(3,
                                new ListNode(4)));
        ListNode merge = new day01().mergeTwoLists(list1,list2);
        while (merge != null){
            System.out.print(merge.val + " ");
            merge = merge.next;
        }
    }
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
    //请必须使用时间复杂度为 O(log n) 的算法
    public int searchInsert(int[] nums, int target) {
        //我的暴力解法，时间复杂度为：O(n)
        int insert = 0;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == target) return i;
            if(nums[i] < target) insert = i+1;
        }
        return insert;
    }
    @Test
    public void test2(){
        int i1 = new day01().searchInsert(new int[]{1, 3, 5, 6}, 5);
        System.out.println(i1);
        int i2 = new day01().searchInsert(new int[]{1, 3, 5, 6}, 2);
        System.out.println(i2);
        int i3 = new day01().searchInsert(new int[]{1, 3, 5, 6}, 3);
        System.out.println(i3);
        int i4 = new day01().searchInsert(new int[]{1, 3, 5, 6}, 7);
        System.out.println(i4);
    }
}
